// Created by WXX on 2021/11/9 10:10
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

/**
 * 执行用时：1528 ms, 在所有 C++ 提交中击败了13.79%的用户
 * 内存消耗：215.7 MB, 在所有 C++ 提交中击败了23.44%的用户
 */
class Solution {
public:
    unordered_map<string, int> f;
    unordered_map<char, int> cnt;
    int ans = 6;

    int findMinStep(string board, string hand) {

        for (auto c : hand) cnt[c]++;
        f[board] = 0;
        dfs(board, get());
        if (ans == 6) ans = -1;
        return ans;
    }

    string get() {  // 返回cnt的字符串表示
        string res;
        for (auto [k, v] : cnt) res += to_string(v);
        return res;
    }

    string clean_up(string s) {  // 进行消除

        bool is_changed = true;
        while (is_changed) {
            is_changed = false;
            for (int i = 0; i < s.size(); i++) {
                int j = i + 1;
                while (j < s.size() && s[j] == s[i]) j++;
                if (j - i >= 3) {
                    s = s.substr(0, i) + s.substr(j);  // [i, j-1]这一段被删除
                    is_changed = true;
                    break;
                }
                i = j - 1;
            }
        }
        return s;
    }

    int h(string board) {  // 启发式函数, 至少还需要多少次操作
        sort(board.begin(), board.end());
        int res = 0;
        for (int i = 0; i < board.size(); ) {
            int j = i + 1;
            while (j < board.size() && board[j] == board[i]) j++;
            if (j - i + cnt[board[i]] < 3) return 6;  // 一定不可能消除完
            if (j - i <= 2) res += 3 - (j - i);
            i = j;
        }
        return res;
    }

    void dfs(string board, string hand) {

        // 剪枝
        if (f[board + ' ' + hand] + h(board) >= ans) return;

        for (auto [k, v] : cnt) {
            if (v) {
                cnt[k]--;
                for (int i = 0; i <= board.size(); i++) {
                    auto r = clean_up(board.substr(0, i) + k + board.substr(i));  // 消除后的字符串
                    auto s = r + ' ' + get();
                    if (f.count(s) == 0 || f[s] > f[board + ' ' + hand] + 1) {
                        f[s] = f[board + ' ' + hand] + 1;
                        if (r.empty()) ans = min(ans, f[s]);  // 说明全部被消除
                        dfs(r, get());
                    }
                }
                cnt[k]++;
            }
        }
    }
};

int main() {

    cout << Solution().findMinStep("WRRBBW", "RB") << endl;  // -1
    cout << Solution().findMinStep("WWRRBBWW", "WRBRW") << endl;  // 2
    cout << Solution().findMinStep("G", "GGGGG") << endl;  // 2
    cout << Solution().findMinStep("RBYYBBRRB", "YRBGB") << endl;  // 3

    return 0;
}
